package LeetCode;

/**
 * @Author by KoVaVo
 * @Date 2023-01-01 13:44
 * @Desc: n皇后的问题
 *
 * 时间复杂度是 n*n
 */
public class code51_nqueen {

    public static int queen(int n){
        if(n < 1 || n > 32){
            return 0;
        }
        //
        int limit = n == 32 ? -1 : (1<<n)-1;
        return process(limit,0,0,0);
    }

    /**
     *
     * @param limit 定义当前的limit。例如：当前的7皇后的问题：生成的对应的字符：0....01111111。后面7个1，前面全是0
     * @param colLim 之前的皇后的影响
     * @param leftDiaLim 左对角线
     * @param rightDiaLim 右对角线
     * @return
     */
    private static int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if(colLim == limit){
            return 1;
        }
        //所有是1的数，都可以去尝试，
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        //找到最右侧的那个1，去尝试
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0){
            mostRightOne =pos &(~pos+1);
            //减去最右侧的1，是为了拿到剩下的1的位置。除了最右侧的那个之外。然后继续用pos的while循环
            pos = pos - mostRightOne;
            res += process(
                    limit,
                    colLim | mostRightOne,
                    (leftDiaLim | mostRightOne)<<1,
                    (rightDiaLim | mostRightOne) >>>1
            );
        }
        return res;
    }

    public static void main(String[] args) {
        int queen = queen(7);
        System.out.println(queen);
    }
}
